public class Test {
    /**
     *  将两个有序链表合并为一个新的有序链表并返回。
     *  新链表是通过拼接给定的两个链表的所有节点组成的。
     */
    public static Node mergeTwoLists(Node head1, Node head2) {
        Node newHead = new Node(-1);
        Node tmpHead = newHead;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val){
                tmpHead.next = head1;
                head1 = head1.next;
                tmpHead = tmpHead.next;
            }else {
                tmpHead.next = head2;
                head2 = head2.next;
                tmpHead = tmpHead.next;
            }
        }
            if (head1 != null){
                tmpHead.next = head1;
            }
            if (head2 != null){
                tmpHead.next = head2;
            }
            return newHead.next;
    }

    /**
     * 输入两个链表，找出它们的第一个公共结点。
     * @param
     */
    public Node getIntersectionNode(Node headA, Node headB) {
        if (headA == null || headB == null) return null;
        int legA = 0;
        int legB = 0;
        Node pl = headA;
        Node ps =headB;
        // 求AB长度
        while (headA != null) {
            legA++;
            pl = pl.next;
        }
        while (headB != null) {
            legB++;
            ps = ps.next;
        }

        pl = headA;
        ps = headB;
        int len = legA - legB;
        if (len < 0){
            pl = headB;
            ps = headA;
            len = legB - legA;
        }
        while (len != 0){
            pl = pl.next;
            len--;
        }
        while (pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        if (pl == null) {
            return null;
        }
        return pl;
    }


    public static void main(String[] args) {
        LinkedList linkedList1 = new LinkedList();
        LinkedList linkedList2 = new LinkedList();
        linkedList1.addFirst(18);
        linkedList1.addFirst(6);
        linkedList1.addFirst(3);
        linkedList1.show();
        System.out.println();
        linkedList2.addFirst(23);
        linkedList2.addFirst(9);
        linkedList2.addFirst(2);
        linkedList2.show();
        System.out.println();
        Node ret = mergeTwoLists(linkedList1.head,linkedList2.head);
        linkedList1.show2(ret);
    }

    public static void main2(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.addFirst(6);
        linkedList.addFirst(5);
        linkedList.addFirst(3);
        linkedList.addFirst(3);
        linkedList.addFirst(2);
        linkedList.show();
        System.out.println();
        linkedList.deleteDuplication();
        linkedList.show();
    }

    public static void main1(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.addFirst(1);
        linkedList.addFirst(2);
        linkedList.addFirst(5);
        linkedList.addFirst(2);
        linkedList.addFirst(1);
        linkedList.show();
        System.out.println();
        System.out.println(linkedList.chkPalindrome());
    }
}
